/**
 * 如果字符串s重排以后，word2能够是其前缀，称s是好的
 * 问word1中有多少个子串是好的
 * 
 * 因为可以重排，所以统计数量即可。
 * 双指针
 * 
 * for i in [0, N):
 *     令right刚好到达满足条件的右边界
 *     则 ans += N - right
 * 循环过程中right始终不减
 * 所以是O(26N)
 */
class Solution {
using _t = array<int, 26>;
public:
    long long validSubstringCount(string word1, string word2) {
        int N = word1.length();
        _t cnt; fill(cnt.begin(), cnt.end(), 0);
        for(auto c : word2){
            cnt[c - 'a'] += 1;
        }

        long long ans = 0;
        int left = 0, right = -1;
        _t vec; fill(vec.begin(), vec.end(), 0);
        while(1){
            while(not isOK(cnt, vec)){
                ++right;
                if(right == N) break;
                vec[word1[right] - 'a'] += 1;
            }
            if(right == N) break;

            ans += N - right;
            
            vec[word1[left] - 'a'] -= 1;
            ++left;
        }
        return ans;
    }

    bool isOK(const _t & a, const _t & b){
        for(int i=0;i<26;++i)if(a[i]>b[i])return false;
        return true;
    }
};